// https://leetcode.cn/problems/contiguous-array/

// 算法思路总结：
// 1. 使用前缀和与哈希表寻找连续子数组
// 2. 将0视为-1，1视为1，计算累计和
// 3. 相同累计和之间的子数组包含相同数量的0和1
// 4. 记录每个累计和首次出现的位置
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        int m = nums.size();
        unordered_map<int, int> up;

        up[0] = -1;

        int ret = 0, sum = 0;
        for (int i = 0 ; i < m ; i++)
        {
            sum += (nums[i] == 0 ? -1 : 1);
            if (up.count(sum) > 0)
            {
                ret = max(ret, i - up[sum]);
            }
            else
            {
                up[sum] = i;
            }
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {0,1,0};
    vector<int> nums2 = {0,1,1,1,1,1,0,0,0};

    Solution sol;

    cout << sol.findMaxLength(nums1) << endl;
    cout << sol.findMaxLength(nums2) << endl;

    return 0;
}